"""P2 2.认识复杂度和简单排序算法"""

from random import random


def select_sort(arr: list):
    """选择排序，时间复杂度O(N^2)，空间复杂度O(1)"""
    len_array = len(arr)
    for i in range(len_array - 1):
        min_index = i
        for j in range(i + 1, len_array):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr


def bubble_sort(arr: list):
    """冒泡排序，时间复杂度O(N^2)，空间复杂度O(1)"""
    for i in range(len(arr) - 1, 1, -1):
        for j in range(i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr


def swap(a: int, b: int):
    """交换两个数的值"""
    a = a ^ b
    b = a ^ b
    a = a ^ b
    return a, b


def print_odd_time_number1(arr: list):
    """arr中有一种数出现奇数次，其他种数出现偶数次，打印出现奇数次的数"""
    ret = 0
    for i in arr:
        ret ^= i
    print(ret)


def print_odd_time_number2(arr: list):
    """arr中有两种数出现奇数次，其他种数出现偶数次，打印出现奇数次的两个数"""
    ret = 0
    for i in arr:
        ret ^= i
    right_one = ret & (~ret + 1)
    only_one = 0
    for i in arr:
        if i & right_one == right_one:
            only_one ^= i
    print(only_one, ret ^ only_one)


def insertion_sort(arr: list):
    """插入排序，时间复杂度O(N^2)，空间复杂度O(1)"""
    for i in range(1, len(arr)):
        for j in range(i-1, -1, -1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr


"""
对数器的概念和使用：
1、有一个你想要测试的方法A
2、有一个复杂度不好但是容易实现的方法B
3、实现一个随机样本生成器
4、把方法A和方法B跑相同的随机样本，看看得到的结果是否一样
5、如果有一个随机样本使得对比结果不一致，打印样本进行人工干预，修改方法A或者方法B
6、当样本数量很多时对比测试依然正确，就可以确定方法A已经正确
"""


def generate_random_array(max_size: int, max_value: int):
    """随机列表生成器"""
    arr = list()
    # int(random() * N)
    # [0, N-1]所有的整数等概率返回一个
    len_array = int(random() * (max_size + 1))
    for i in range(len_array):
        arr.append(
            int(random() * (max_value + 1)) - int(random() * (max_value + 1))
        )
    return arr


if __name__ == "__main__":
    sort_array = [3, 4, 5, 4, 1, 9]
    print(select_sort(sort_array))
    print(bubble_sort(sort_array))
    print(swap(5, 7))
    odd_array1 = [1, 1, 4, 5, 8, 8, 5]
    print_odd_time_number1(odd_array1)
    odd_array2 = [3, 3, 4, 5, 8, 9, 8, 5]
    print_odd_time_number2(odd_array2)
    print(insertion_sort(sort_array))
    print(generate_random_array(10, 100))
